{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Depth of BST Given Insertion Order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #binary-tree #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #二叉树 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDepthBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给定二叉搜索树的插入顺序求深度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个<strong>从 0 开始索引</strong>的整数类型数组 <code>order</code> ，其长度为 <code>n</code>，是从 <code>1</code> 到 <code>n</code> 的所有整数的一个排列，表示插入到一棵二叉搜索树的顺序。</p>\n",
    "\n",
    "<p>二叉搜索树的定义如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一个节点的左子树只包含键值<strong>小于</strong>该节点键值的节点。</li>\n",
    "\t<li>一个节点的右子树只包含键值<strong>大于</strong>该节点键值的节点。</li>\n",
    "\t<li>左子树和右子树须均为二叉搜索树。</li>\n",
    "</ul>\n",
    "\n",
    "<p>该二叉搜索树的构造方式如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>order[0]</code> 将成为该二叉搜索树的根。</li>\n",
    "\t<li>所有后续的元素均在维持二叉搜索树性质的前提下作为<strong>任何</strong>已存在节点的<strong>子节点</strong>插入。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回该二叉搜索树的<strong>深度</strong>。</p>\n",
    "\n",
    "<p>一棵二叉树的<strong>深度</strong>是从根节点到最远叶节点的<strong>最长路径</strong>所经<strong>节点</strong>的个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/15/1.png\" style=\"width: 624px; height: 154px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> order = [2,1,4,3]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释: </strong>该二叉搜索树的深度为 3，路径为 2-&gt;4-&gt;3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/15/2.png\" style=\"width: 624px; height: 146px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> order = [2,1,3,4]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释: </strong>该二叉搜索树的深度为 3，路径为 2-&gt;3-&gt;4。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/15/3.png\" style=\"width: 624px; height: 225px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> order = [1,2,3,4]\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释: </strong>该二叉搜索树的深度为 4，路径为 1-&gt;2-&gt;3-&gt;4。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == order.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>order</code> 是从 <code>1</code> 到 <code>n</code> 的整数的一个排列。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [depth-of-bst-given-insertion-order](https://leetcode.cn/problems/depth-of-bst-given-insertion-order/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [depth-of-bst-given-insertion-order](https://leetcode.cn/problems/depth-of-bst-given-insertion-order/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4,3]', '[2,1,3,4]', '[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxDepthBST(self, order: List[int]) -> int:\n",
    "        n = len(order)\n",
    "        s = SortedList()\n",
    "        dp = [0] * (n + 2)\n",
    "        s.add(0)\n",
    "        s.add(n + 1)\n",
    "        for num in order:\n",
    "            idx = s.bisect_left(num)\n",
    "            dp[num] = max(dp[s[idx - 1]], dp[s[idx]]) + 1\n",
    "            s.add(num)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxDepthBST(self, order: List[int]) -> int:\n",
    "        s = SortedList()\n",
    "        n=len(order)\n",
    "        dp=[0]*(n+2)\n",
    "        s.add(0)\n",
    "        s.add(n+1)\n",
    "        for i in order:\n",
    "            ind=s.bisect_left(i)\n",
    "            dp[i]=max(dp[s[ind-1]],dp[s[ind]])+1\n",
    "            s.add(i)\n",
    "        return max(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "        # n=len(order)\n",
    "        # if n==0:\n",
    "        #     return 0\n",
    "        # if n==1:\n",
    "        #     return 1\n",
    "        # left=[]\n",
    "        # right=[]\n",
    "        # for num in order[1:]:\n",
    "        #     if num<order[0]:\n",
    "        #         left.append(num)\n",
    "        #     else:\n",
    "        #         right.append(num)\n",
    "        # return 1+max(self.maxDepthBST(left),self.maxDepthBST(right))\n",
    "    \n",
    "    def maxDepthBST(self, order: List[int]) -> int:\n",
    "        s = SortedList()\n",
    "        n=len(order)\n",
    "        dp=[0]*(n+2)\n",
    "        s.add(0)\n",
    "        s.add(n+1)\n",
    "        for i in order:\n",
    "            ind=s.bisect_left(i)\n",
    "            dp[i]=max(dp[s[ind-1]],dp[s[ind]])+1\n",
    "            s.add(i)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthBST(self, order: List[int]) -> int:\n",
    "        n = len(order)\n",
    "        depth = [0]*(n+1)\n",
    "        pre = SortedList([0, n+1])\n",
    "        for num in order:\n",
    "            i = pre.bisect_right(num) - 1\n",
    "            depth[num] = depth[pre[i]] + 1\n",
    "            depth[pre[i]] += 1\n",
    "            pre.add(num)\n",
    "        return max(depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxDepthBST(self, order: List[int]) -> int:\n",
    "        s = SortedList()\n",
    "        n=len(order)\n",
    "        dp=[0]*(n+2)\n",
    "        s.add(0)\n",
    "        s.add(n+1)\n",
    "        for i in order:\n",
    "            ind=s.bisect_left(i)\n",
    "            print(ind)\n",
    "            dp[i]=max(dp[s[ind-1]],dp[s[ind]])+1\n",
    "            s.add(i)\n",
    "        return max(dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthBST(self, order: List[int]) -> int:\n",
    "        ans = 1\n",
    "        sl = SortedList([[inf,order[0], 1], [order[0], -inf, 1]])\n",
    "        for i in range(1, len(order)):\n",
    "            x = order[i]\n",
    "            i = sl.bisect_left([x, 0, 0])\n",
    "            l, r, c = sl.pop(i)\n",
    "            sl.add([l, x, c+1])\n",
    "            sl.add([x, r, c+1])\n",
    "            ans = max(ans, c+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from bisect import bisect_left, bisect_right\n",
    "from collections import defaultdict\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthBST(self, order: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param order:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        sd1= SortedList()\n",
    "        sd1.add(0)\n",
    "        sd1.add(len(order)+1)\n",
    "        df = defaultdict(int)\n",
    "        for i in order:\n",
    "            idx = sd1.bisect_left(i)\n",
    "            val1 = sd1[idx]\n",
    "            val2 = sd1[idx-1]\n",
    "            df[i] = max(df[val1], df[val2]) + 1\n",
    "            sd1.add(i)\n",
    "        return max(df.values())\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
